﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace ns
{
    public class TreeQuestion : MonoBehaviour
    {
        //98. 验证二叉搜索树
        //https://leetcode-cn.com/problems/validate-binary-search-tree/
        //递归，递归函数
        //
        public bool IsValidBST(TreeNode root)
        {
            return helper(root, -1, -1);
        }
        public bool helper(TreeNode node, int lower, int upper) //节点，下限 和 上限
        {
            if (node == null)
            {
                return true;
            }
            int val = node.val;

            if (lower != -1 && val <= lower) //下限大于 根节点
            {
                return false;
            }
            if (upper != -1 && val >= upper) //上限小于 根节点
            {
                return false;
            }

            if (!helper(node.right, val, upper))  //右子树，根节点下限，无上限
            {
                return false;
            }
            if (!helper(node.left, lower, val)) //左子树，根节点上限，无下限
            {
                return false;
            }
            return true;
        }

        //104. 二叉树的最大深度
        //https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/
        //递归,自己调用自己
        //
        public int MaxDepth(TreeNode root)
        {
            if (root == null)
            {
                return 0;
            }
            else
            {
                int maxleft = MaxDepth(root.left);
                int maxright = MaxDepth(root.right);
                return System.Math.Max(maxleft, maxright) + 1;
            }
        }

        //108. 将有序数组转换为二叉搜索树
        //https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
        //二叉搜索树的中序遍历，确认根节点，通过递归确认二叉平衡树，下标范围
        //
        public TreeNode1 SortedArrayToBST(int[] nums)
        {
            return helper(nums, 0, nums.Length - 1);
        }

        public TreeNode1 helper(int[] nums, int left, int right) //数组，左下标和右下标
        {
            if (left > right)
            {
                return null;
            }

            // 总是选择中间位置左边的数字作为根节点
            int mid = (left + right) / 2;

            TreeNode1 root = new TreeNode1(nums[mid]); //获取root的值
            root.left = helper(nums, left, mid - 1); //左子树
            root.right = helper(nums, mid + 1, right); //右子树
            return root;
        }
    }
}


public class TreeNode
{
    public int val; //值
    public TreeNode left; //左节点
    public TreeNode right; //右节点
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


public class TreeNode1
{
    public int val;
    public TreeNode1 left;
    public TreeNode1 right;
    public TreeNode1(int x) { val = x; }
}
